package top100.linklist;


import datastructure.linklist.ListNode;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/22 8:24
 * @description:
 */
public class Solution234 {
    public boolean isPalindrome(ListNode head) {
        if(head == null){
            return true;
        }
        ListNode slow = head;
        ListNode fast = head;
        //1 slow =1, fast= 1
        //1,2 slow=1 fast =1
        //1,2,3 slow = 2 fast = 3
        //1,2,3,4  slow = 2 fast=3
        //1,2,3,4,5 slow= 3 fast =5
        while (fast.next != null && fast.next.next != null) {
            //在里面判断fast.next.next != null会导致fast不走陷入死循环
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode newHead = reverse(slow.next);
        ListNode p1 = head;
        ListNode p2 = newHead;
        boolean result = true;
        while (p2 != null) {
            if (p1.val != p2.val) {
                result = false;
                break;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        reverse(newHead);
        return result;
    }

    public ListNode reverse(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode dummy = new ListNode(-1);
        ListNode p = head;
        while (p != null) {
            ListNode temp = p;
            p = p.next;
            temp.next = dummy.next;
            dummy.next = temp;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 1, 2, 1};
        Solution234 solution = new Solution234();
        ListNode head = ListNode.arrayToList(nums);
        boolean res = solution.isPalindrome(head);
        System.out.println(res);
        ListNode.printList(head);
    }
}
